/* 
	file listing 
	by Clint Webb <webb.clint@gmail.com>
	(c) Copyright Clinton Webb, 2008.
	
	Released under terms of the GPLv3 licence.

	This tool is used to generate a listing of files and directories.  It works 
	similar to 'ls -Ral' except each file is listed with its full path, and on a 
	single line.  This makes it more useful for grep.

	A function that might be added in the future would be where you can specify a mask 
	to only return files that match.  It will always look at each directory (ie, the 
	mask doesn't apply to the directory name).

	Finally, the code will make a note of the inodes of directories in the path so 
	that it doesn't get stuck in a loop, if there are symbolic links.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <dirent.h>
#include <unistd.h>
#include <assert.h>
#include <dirent.h>
#include <fnmatch.h>
#include <errno.h>

/* Check that the NAME_MAX setting has already been defined, and at least something */
#if (NAME_MAX < 64)
#error Really?
#endif


/* The number of directories deep that we will recurse. */
#define MAX_DEPTH	128
#define MAX_PATH	(MAX_DEPTH*(NAME_MAX+1))

/* 
   For any lengthy opertions (such as scanning an entire file system), 
   we will end up checking the inode list a LOT.  To improve this 
   somewhat, I am adding multiple inode tables, based on the 
   least-significant bits.  This way we will already have some knowledge 
   about which table the inode will be in.  This is purely a porformance 
   enhancement, and testing of different number of tables has determined 
   that the biggest gain is done by having 2 tables.  Additional tables 
   add slight gain, but not significant. 
*/
#define ALLOC_INC	1024
#define INODE_TABLES	2



ino_t *ilist=NULL;
unsigned int ilen=0;
unsigned int imax=0;
static unsigned int iloops=0;

int is_new_inode(ino_t inode)
{
	int found=0;
	int i;

	for(i=0; i<ilen && found==0; i++) {
		iloops++;

		if (ilist[i] == inode) {
			found ++;
		}
	}

	if (found == 0) {
		if (ilen == imax) {
			imax += ALLOC_INC;
			ilist = (ino_t *) realloc(ilist, sizeof(ino_t) * imax);
		}
		ilist[ilen] = inode;
		ilen++;
	}

	return(found);
}


int main(int argc, char **argv)
{
	int retcode=0;
	int depth=0;
	int c;
	int result;
	struct {
		short all;
		short full;
		int mask;
	} settings;

	char **qlist=NULL;
	unsigned int qlen=0;
	unsigned int qmax=0;
	unsigned int qstore=0;
	char *qpath;

	DIR *dir;

	struct dirent *detail;
	int filter=0;

	/* Initialise our settings with defaults */
	settings.all = 0;
	settings.full = 0;
	settings.mask = 0;


	
	/* First we need to check the command line options. */
	while ((c = getopt(argc, argv, "af")) != -1) {
        switch (c) {
        	case 'a':
				settings.all = 1;
				break;
        	case 'f':
				settings.full = 1;
				break;
		}
	}

	/* Now we need to see if there is a mask left in the command line */
	if (optind < argc) {
		settings.mask = optind;
	}

	/* Add the current directory to our search path.   Should we list it from the 
	   current directory down, or should we display the full path? */

	qmax = ALLOC_INC;
	qlist = (char **) malloc(sizeof(char *)*qmax);
	assert(qlist != NULL);
	qlen = 1;
	if (settings.full == 0) {
		/* We want relative listings, so we will just add "." to the list." */
		qlist[0] = (char *) malloc(2);
		assert(qlist[0] != NULL);
		strcpy(qlist[0], ".");
	}
	else {
		/* We want a full path, so we get the current path, and add it to the list.  */
		qlist[0] = (char *) malloc(MAX_PATH+1);
		assert(qlist[0] != NULL);
		getcwd(&qlist[0][0], MAX_PATH);
	}

	/* Now that we have all the settings we are looking for, we will open the current 
	   directory and start recursing through it. */	

	do {
	
		// since we are processing the last one in the queue, we 
		// can decrement our counter now.  As soon as we have done 
		// the directory listing, we will be removing it.
		assert(qlen > 0);
		qlen--;
		assert(qlen >= 0);
		assert(qlen < qmax);
		assert(qlist[qlen] != NULL);
		
		// open a directory handler.
// 		printf("Opening Dir: %s\n", qlist[qlen]);
		dir = opendir(qlist[qlen]);
		if (dir == NULL) {
			switch(errno) {
				case EACCES:	printf("%s: Permission denied.\n",qlist[qlen]);				break;
				case EBADF:	printf("fd is not a valid file descriptor opened for reading.\n");	break;
				case EMFILE:	printf("Too many file descriptors in use by process.\n");		break;
				case ENFILE:	printf("Too many files are currently open in the system.\n");		break;
				case ENOENT:	printf("Directory does not exist, or name is an empty string.\n");	break;
				case ENOMEM:	printf("Insufficient memory to complete the operation.\n");		break;
				case ENOTDIR:	printf("name is not a directory.\n");					break;
				default:	printf("other\n");							break;
			}
			
			free(qlist[qlen]);
		}
		else {
				
			// store the path.  We need to decouple it from the list because new entries will probably be made.
			qstore = qlen;
			qpath = qlist[qlen];
			qlist[qlen] = NULL;
	
			while (detail = readdir(dir)) { 
		
				assert(detail->d_ino > 0);
	
	
				// if the entry is a directory...
				if (detail->d_type & DT_DIR) {
					if (is_new_inode(detail->d_ino) == 0) {
				
						filter = 0;
						
						// We need to add this new directory to our queue.
						if (detail->d_name[0] == '.') {
							if (detail->d_name[1] == '\0' || (detail->d_name[1] == '.' && detail->d_name[2] == '\0')) {
								filter = 1;
							}
							else if (settings.all == 0) {
								filter = 1;
							}
						}
						
						if (filter == 0) {
							if (qlen >= qmax) {
								assert(qlist != NULL);
								qmax += ALLOC_INC;
								qlist = (char **) realloc(qlist, sizeof(char *)*qmax);
								assert(qlist != NULL);
							}
							qlist[qlen] = (char *) malloc(strlen(qpath)+strlen(detail->d_name)+2);
							assert(qlist[qlen] != NULL);
							sprintf(qlist[qlen], "%s/%s", qpath, detail->d_name);
							qlen++;
	
						}
					}
				}
				else {
					
					// use fnmatch to check the mask if some was supplied.
					filter = 0;		
					
					if (filter == 0) {
						assert(qpath != NULL);
						printf("%s/%s\n", qpath, detail->d_name);
					}
				}
			}
			
			
			/* This way we will end up with the directories 
			   in the reverse order (because we will be 
			   traversing from the end of the queue).  We will 
			   need to do some trickery to get the directories 
			   in the correct order so they can be picked off 
			   the end of the queue. 
			*/ 
			
			/* I've just discovered that the directories are 
			   not returned in alphabetic order anyway.  I'll 
			   keep this code in for now, but will probably 
			   want to sort it based on alpha.
			*/
			
			
			if ((qlen-1) > qstore) {
				int aa=qstore;
				int bb=qlen-1;
				char *pp;
				
				while(aa < bb) {
					pp = qlist[aa];
					qlist[aa] = qlist[bb];
					qlist[bb] = pp;
					aa++;
					bb--;
				}
			}
			
			assert(qpath != NULL);
			free(qpath);
			
			assert(dir != NULL);
			result = closedir(dir);
			assert(result == 0);
			dir = NULL;
		}		
	} while (qlen > 0);
	assert(qlen == 0);

	
//	printf("\n\nTotal Inodes stored: %d\n", ilen);
//	printf("Total Inode Loops: %u\n\n", iloops);

	if (qlist != NULL) { free(qlist); }
	if (ilist != NULL) { free(ilist); }

	return (retcode);
}
